var qian = ['a','c','f','g','b','d','e'];
var zhong = ['f','c','g','a','d','b','e'];

function Node(value) {
	this.value = value;
	this.left = null;
	this.right = null
}

/*
* 找到根节点在中序遍历中的位置
* 先序遍历的（左 右）子树
* 中序遍历的（左 右）子树
*根据左子树的前序和中序 还原左子树并赋值给root.left
*根据右子树的前序和中序 还原左子树并赋值给root.right
* */

function f1(qian,zhong) {
	if(qian === null || zhong === null ||
		qian.length === 0 || zhong.length === 0
		|| qian.length !== zhong.length) return null;

		var root = new Node(qian[0]);
		var index = zhong.indexOf(root.value);      //找到根节点在中序遍历中的位置
		var qianLeft = qian.slice(1, 1 + index);     //先序遍历的左子树
		var qianRight = qian.slice(1 + index, qian.length); //先序遍历的右子树
		var zhongLeft = zhong.slice(0, index);       //中序遍历的左子树
		var zhongRight = zhong.slice(1 + index, zhong.length); //中序遍历的右子树

		root.left = f1(qianLeft,zhongLeft);         //根据左子树的前序和中序 还原左子树并赋值给root.left
		root.right = f1(qianRight, zhongRight);     //根据右子树的前序和中序 还原右子树并赋值给root.right
		return root
}

var root = f1(qian,zhong)
console.log(root.left)
console.log(root.right)

/*
Node {
	value: 'c',
		left: Node { value: 'f', left: null, right: null },
	right: Node { value: 'g', left: null, right: null }
}
Node {
	value: 'b',
		left: Node { value: 'd', left: null, right: null },
	right: Node { value: 'e', left: null, right: null }
*/
